package Graph.Medium;

import java.util.*;

public class LC0399 {
    static final double eps = 1E-6;

    private class Edge {
        String variable;
        double value;

        public boolean equals(Edge obj) {
            return (variable.equals(obj.variable) && Math.abs(value - obj.value) < eps);
        }

        public Edge(String variable, double value) {
            this.variable = variable;
            this.value = value;
        }
    }

    TreeMap<String, HashSet<Edge>> adjSets = new TreeMap<>(); // 集合形式的邻接表

    /**
     * 程序入口
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 构建邻接表
        for (int i = 0; i < equations.size(); i++) {
            Object[] parseResult = parseEquation(equations.get(i), values[i]);
            String var1 = ((String[]) parseResult[0])[0], var2 = ((String[]) parseResult[0])[1];
            double value = (double) parseResult[1];
            adjSets.putIfAbsent(var1, new HashSet<>());
            adjSets.get(var1).add(new Edge(var2, value));
            adjSets.putIfAbsent(var2, new HashSet<>());
            adjSets.get(var2).add(new Edge(var1, 1 / value));
        }

        double[] ret = new double[queries.size()];
        // 除法求解
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            Object[] parseResult = parseEquation(query, 1);
            String var1 = ((String[]) parseResult[0])[0], var2 = ((String[]) parseResult[0])[1];

            if (!adjSets.containsKey(var1) || !adjSets.containsKey(var2)) {
                ret[i] = -1;
                continue;
            }
            if (var1.equals(var2)) {
                ret[i] = 1;
                continue;
            }

            double value = 1 / (double) parseResult[1];

            // DFS
            TreeMap<String, Boolean> visited = new TreeMap<>();
            for (String var : adjSets.keySet()) visited.put(var, Boolean.FALSE);
            visited.put(var1, Boolean.TRUE);
            ret[i] = value * dfs(var1, var2, visited, 1.0);
        }

        return ret;
    }

    /**
     * 深度优先搜索寻找var->target的路径
     */
    private double dfs(String var, String target, TreeMap<String, Boolean> visited, double value) {
        HashSet<Edge> adjSet = adjSets.get(var);
        for (Edge edge : adjSet) {
            String nextVar = edge.variable;
            if (visited.get(edge.variable) == Boolean.TRUE) continue;

            if (edge.variable.equals(target)) {
                value *= edge.value;
                return value;
            }

            visited.put(nextVar, Boolean.TRUE);
            double dfsResult = dfs(nextVar, target, visited, value * edge.value);
            if (dfsResult > 0) return dfsResult;
        }

        return -1; // 找不到var->target的路径
    }

    // 解析等式，转化为分子和分母只有变量的形式，并返回此形式下除法运算的值
    // 假设：如果存在数字，那么数字位于变量之前
    // 返回值：{String[], Double}，其中String[]存储了分别为分子和分母的字符串形式的变量
    private Object[] parseEquation(List<String> equation, double value) {
        // 解析数字
        int idx = 0;
        String expression = equation.get(0);
        for (; idx < expression.length(); idx++) {
            if (!(expression.charAt(idx) >= '0' && expression.charAt(idx) <= '9')) break;
        }
        double coefficient1 = idx > 0 ? Double.parseDouble(expression.substring(0, idx)) : 1.0;
        String expression1 = idx > 0 ? expression.substring(idx) : expression;
        expression = equation.get(1);
        idx = 0;
        for (; idx < expression.length(); idx++) {
            if (!(expression.charAt(idx) >= '0' && expression.charAt(idx) <= '9')) break;
        }
        double coefficient2 = idx > 0 ? Double.parseDouble(expression.substring(0, idx)) : 1.0;
        String expression2 = idx > 0 ? expression.substring(idx) : expression;
        value = value * coefficient2 / coefficient1;

        Object[] ret = new Object[2];
        ret[0] = new String[2];
        ((String[]) ret[0])[0] = expression1;
        ((String[]) ret[0])[1] = expression2;
        ret[1] = value;

        return ret;
    }

    public static void main(String[] args) {
        String[][] equationsAsArray = new String[][]{{"a", "b"}, {"b", "c"}};
        double[] values = new double[]{2, 3};
        String[][] queriesAsArray = new String[][]{{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
        LC0399Legacy solution = new LC0399Legacy();
        List<List<String>> equations = new ArrayList<>();
        List<List<String>> queries = new ArrayList<>();
        for (String[] equation : equationsAsArray) {
            equations.add(Arrays.asList(equation));
        }
        for (String[] query : queriesAsArray) {
            queries.add(Arrays.asList(query));
        }
        double[] answers = solution.calcEquation(equations, values, queries);
        System.out.println();
    }
}
